
// 0.169-达到目标值
// 1.基础-455-分发饼干
// 2.基础-1005-k次取反后最大化的数组和
// 3.基础-860-柠檬水找零
// 4.序列问题-376-摆动序列
// 5.序列问题-738-单调递增的数字
// 6.两个维度权衡-135-分发糖果
// 7.两个维度权衡-406-根据身高重建队列
// 8.区间问题-55-跳跃游戏
// 9.区间问题-45-跳跃游戏2
// 10.区间问题-452-最少数量的箭射气球
// 11.区间问题-435-无重叠区间
// 12.区间问题-56-合并区间
// 13.区间问题-763-划分字母区间
// 14.子序列(连续)-674-最长连续递增
// 15.子序列(连续)-53-最大子序和
// 16.编辑距离-392-判断子序列

// 17.股票-121-买卖股票的最佳时机
// 18.股票-122-买卖股票的最佳时机2
// 19.股票-714-买卖股票的最佳时机3
// 20. 单调递增的数字




// 0. 达到目标值
var minMoves = function(target, maxDoubles) {
  let count = 0;

  while(target > 1 && maxDoubles){
      if(target%2 === 0){
          target = target / 2
          count++
          maxDoubles--
      } else {
          target = target - 1
          count++
      }
  }
  if(target>1) {
      count+=target-1;
  }
  return count
};


// 1. 孩子胃口匹配
// 贪心：优先大胃口匹配大饼干 倒叙循环胃口 g: 胃口 s：饼干
// 题解：尽可能多满足孩子胃口 
// 思路：先给胃口和饼干排序，倒序循环胃口，当饼干大于等于胃口时， 结果++，饼干消耗index--，返回结果
// 注意：饼干和胃口都是倒序
var findContentChildren = (g, s) => {
  g.sort((a, b) => a - b)
  s.sort((a, b) => a - b)
  let res = 0;
  let index = s.length - 1;
  for (let i = g.length - 1; i >= 0; i--) { // 倒叙循环的胃口
    if (index >= 0 && s[index] >= g[i]) {
      res++;
      index--
    }
  }
  return res
}
console.log(findContentChildren([1, 2, 3], [1, 1]))


// 2. k次取反后的最大值
// 题解：有正有负的数组，k次取反后和最大
// 思路：先绝对值排序，然后优先反转负数，反转后还有正数，则先反转最小的，绝对值排序后最小的在最后
// 注意：可多次旋转一个下标
var largestSumAfterKNegations = (nums, k) => {
  nums.sort((a, b) => Math.abs(b) - Math.abs(a)) // 处理完负数后还是有序
  // 优先处理大的负数
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] < 0 && k > 0) {
      nums[i] = - nums[i]
      k--
    }
  }
  // k没处理完，继续处理最小数
  while (k > 0) {
    nums[nums.length - 1] = - nums[nums.length - 1];
    k--
  }
  return nums.reduce((pre, cur) => (pre + cur), 0)
}
// nums = [4,2,3], k = 1
console.log(largestSumAfterKNegations([4, 2, 3], 1))

// 3. 柠檬水找零 5 10 20
// 题解：5块一杯，数组内每个item表示每次收到的钱，一次买一杯， 看能否找零成功，转化为5元，10元，是否是否会出现负数
// 思路：当5收到5元，five++；当收到十元，five为<=0,false，否则five--，ten++；当收到20，ten和five都有，则都--，只有five，five-3，都没有false
// 注意：不同状态做好判断
var lemonadeChange = (bills) => {
  let fiveCount = 0;
  let tenCount = 0;
  for (let i = 0; i < bills.length; i++) {
    if (bills[i] === 5) {
      fiveCount++
    } else if (bills[i] === 10) {
      if (fiveCount <= 0) return false
      tenCount++;
      fiveCount--;
    } else {
      if (tenCount > 0 && fiveCount > 0) {
        tenCount--;
        fiveCount--;
      } else if (fiveCount >= 3) { // five 比较特殊
        fiveCount -= 3
      } else {
        return false
      }
    }
  }
}
// console.log(lemonadeChange([5, 5, 10, 10, 20]))
console.log(lemonadeChange([5, 5, 5, 10, 5, 5, 10, 20, 20, 20]))

// 4. 摆动序列
// 保存上一次的差值, 对比当前差值
// 允许跳过
// 题解：差值+-，就是摆动序列， 子序列不需要连续
// 思路：存两个状态，pre，cur；cur为num[i+1]-num[i]; 当cur<0,pre>0||cur>0,pre< 0 则成立，结果++，cur赋值给pre
// 注意：循环要-1 避免越界
var wiggleMaxLength = (nums) => {
  if (nums.length <= 1) return nums.length
  let preDiff = 0;
  let count = 1;
  for (let i = 0; i < nums.length - 1; i++) {
    let curDiff = nums[i + 1] - nums[i]
    if ((preDiff >= 0 && curDiff < 0) || (preDiff <= 0 && curDiff > 0)) {
      count++
      preDiff = curDiff
    }
  }
  return count
}
console.log(wiggleMaxLength([1, 7, 4, 9, 2, 5]))


// 5. 两个维度的权衡 身高队列排序
// 优先确定身高维度，然后根据k去插入，确定一个维度再处理另一个维度
// 题解：0 是身高，1 是前面有几个比他高的
// 思路：优先排身高，再按k排列；最后按照k插入 queue.splice(people[i][1], 0, people[i])
// 注意：// 先插的身高肯定比目标高
var resconstractQueue = (people) => {
  let queue = [];
  people.sort((a, b) => {
    if (a[0] !== b[0]) {
      return b[0] - a[0] // 高的放前面
    } else {
      return a[1] - b[1]
    }
  })

  for (let i = 0; i < people.length; i++) {
    queue.splice(people[i][1], 0, people[i])
  }
  return queue
}
console.log(resconstractQueue([[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]]))


// 6. 两个维度的权衡 分发糖果
// 题解：每个小孩，左右两边得分高的都要比他糖多， 最少糖
// 思路：先确定右边，比前一个大（i-1）则+1；再确定左边，要倒序，比后一个要大（i+1）则 res[i] = Math.max(res[i], res[i + 1] + 1)
// 注意：正序，倒序，两边都要留索引空位
var candy = (ratings) => {
  let res = new Array(ratings.length).fill(1)

  // 两个维度先确定一边, 先确定右边侧
  for (let i = 1; i < ratings.length; i++) {
    if (ratings[i] > ratings[i - 1]) {
      res[i] = res[i - 1] + 1
    }
  }
  // 确定左边，倒叙 
  for (let i = ratings.length - 2; i >= 0; i--) { // 最后一个索引ratings.length -1，最后一位不取 -1
    if (ratings[i] > ratings[i + 1]) {
      res[i] = Math.max(res[i], res[i + 1] + 1)
    }
  }

  return res.reduce((pre, cur) => pre + cur, 0)
}
console.log('candy', candy([1, 0, 2]))


// 7. 跳跃问题
// 题解：每个元素表示在当前位置可跳的最大范围
// 思路：保存每个元素能到达的最大cover,当cover>= nums.length -1 则已经到达范围返回true
// 注意：循环是<=cover
var canJump = (nums) => {
  if (nums.length === 1) return true;
  let cover = 0;
  for (let i = 0; i <= cover; i++) { // 结束为止为cover 需要注意
    cover = Math.max(cover, i + nums[i])
    if (cover >= nums.length - 1) return true;
  }
}
console.log(canJump([2, 3, 1, 1, 4]))

// 8. 跳跃问题2
// 题解：最小步数到达终点， 转化为可覆盖范围
// 思路：保存每个元素能到达的最大cover, 当i与curIndex相等时，则表示当前步数已到达最远位置，步数++，curIndex更新为新cover
// 注意：循环< nums.length-1, 当到达最后一个时会多加一步
var canJump2 = (nums) => {
  let curIndex = 0;
  let cover = 0;
  let step = 0;
  for (let i = 0; i < nums.length - 1; i++) {
    cover = Math.max(cover, nums[i] + i); // 暂存第n步区间， n+1步可到达的最远距离
    if (i === curIndex) { // 已经到达最大，继续延伸需要增加步数
      curIndex = cover;
      step++;
    }
  }
  return step
}
console.log('跳跃2', canJump2([2, 3, 1, 1, 4]))

// 9. 最小数量射击气球 
// 题解：区域重叠，用最少得箭覆盖所有区域，找到有几个不重叠的区域
// 思路：按照最右边大小排序，然后左边比较max，如果左边大于max则max更新为当前索引的右边，箭++
// 注意：先排序，max是右边取值
var findMinArrowShots = (arr) => {
  arr.sort((a, b) => a[1] - b[1]);
  let max = arr[0][1];
  let count = 1;
  for (let i = 0; i < arr.length; i++) {
    if (arr[i][0] > max) { 
      max = arr[i][1]
      count++
    }
  }
  return count
}
console.log(findMinArrowShots([[10, 16], [2, 8], [1, 6], [7, 12]]))

// 10.无重叠区间 
// 题解：移除多少个区间使剩余区间不重合
// 思路：找到有多少个不重叠的区域，然后总数-不重叠的 =需要移除的
// 注意：重叠区域都需要移除，转换法
var eraseOverlapIntervals = (arr) => {
  arr.sort((a, b) => (a[1] - b[1]))
  let max = arr[0][1]
  let count = 1; // 不重合的区间
  for (let i = 0; i < arr.length; i++) { 
    if (arr[i][0] >= max) { // 边界值==
      max = arr[i][1]
      count++
    }
  }
  return arr.length - count // 总数-不重叠 = 需要移除的
}
console.log(eraseOverlapIntervals([[1, 2], [2, 3], [3, 4], [1, 3]]))

// 11. 合并区间
// 题解：将重叠的部分合并，区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
// 思路：排序；声明一个pre，循环获取cur，比较cur左边是否在pre右边内，若是则更新右边：prev[1] = Math.max(prev[1], cur[1])；不在则pre放入结果，并更新pre为cur
// 注意：循环结束后要将pre push进结果
var merge = (arr) => {
  arr.sort((a, b) => a[0] - b[0]);
  let prev = arr[0];
  let res = [];
  for (let i = 0; i < arr.length; i++) {
    let cur = arr[i];
    if (cur[0] > prev[1]) { // 不重叠则旧的放入结果，创建新的prev
      res.push(prev)
      prev = cur
    } else {
      prev[1] = Math.max(prev[1], cur[1])
    }
  }
  res.push(prev)
  return res;
}
console.log(merge([[1, 3], [2, 6], [8, 10], [15, 18]]))

// 12. 划分字母区间
// 题解：当前 其他范围内不会出现 此区间字母，返回的是各个切片的长度, 【相同的字母只会出现在同一个区间里】
// 思路：用map存下每个字母的最远位置，循环当前最远与历史最远比较获取此区间cover的最远距离，当i= cover时，说明此区间的字母不会出现在别的区间，则存入长度i-start+1，start更新为i+1
// 注意：【相同的字母只会出现在同一个区间里】
const partitionLabels = (s) => {
  const maxPos = {};
  for (let i = 0; i < s.length; i++) { // 存放字母所在的最远位置
    maxPos[s[i]] = i
  }

  const res = [];
  let start = 0; // 起始切割位置
  let cover = 0; // 已经扫描的最远位置

  for (let i = 0; i < s.length; i++) {
    cover = Math.max(cover, maxPos[s[i]]); // 当前最远与历史最远对比
    if (i === cover) {
      res.push(i - start + 1);
      start = i + 1
    }
  }
  return res
}
console.log(partitionLabels("ababcbacadefegdehijhklij"))

// 13.最长连续递增子串-最长上升子串-连续
// 题解：最长上升子串，返回长度
// 思路：通过收集所有上坡片段的长度，取其中最大值即为本题答案，当当前位置比前一个小起始位置变更，res=Math.max(res, i-start+1)
// 注意：start的含义
var findLengthOfLCIS = (nums) => {
  let res = 0;
  const n = nums.length;
  let start = 0;
  for (let i = 0; i < n; i++) {
    if (i > 0 && nums[i] <= nums[i - 1]) {
      start = i
    }
    res = Math.max(res, i - start + 1)
  }
  return res;
}
console.log(findLengthOfLCIS([1, 3, 5, 4, 7]))

// 14.最大子串和 -连续 （连续数组最大的和）
// 题解：从一段有正有负的数组中截取一段，连续的子串，求和最大
// 思路：将每个item变位当前位置最大和，Math.max(nums[i - 1] + nums[i], nums[i])，然后计算max最大Math.max(max, nums[i])
// 注意：两个max
var maxSubArray = (nums) => {
  var max = nums[0];
  for (let i = 1; i < nums.length; i++) {
    nums[i] = Math.max(nums[i - 1] + nums[i], nums[i]) // 这里注意是和当前位置nums[i]比较
    max = Math.max(max, nums[i])
  }
  return max
}
console.log(maxSubArray([5, 4, -1, 7, 8]))


// 15.乘积最大子数组 （连续数组最大的乘积）
var maxProduct = function(nums) {
  let min = nums[0];
  let max = nums[0];
  let res = nums[0];

  for(let i =1 ; i< nums.length; i++){
      let temp = min;
      min = Math.min(nums[i], Math.min(min* nums[i], max *nums[i]))
      max = Math.max(nums[i], Math.max(temp * nums[i], max* nums[i]))

      res = Math.max(res, max)
  }
  return res
};

// 16.判断子序列-不连续
// 题解："ace"是"abcde"的一个子序列，而"aec"不是）
// 思路：快慢指针，while，相等的时候慢指针变化，
// 注意：结果慢指针是否等于短s长度
var isSubQuence = (s, t) => {
  let i = 0;
  let j = 0;
  while (i < s.length && j < t.length) {
    if (s[i] === t[j]) i++
    j++
  }
  return i === s.length
}
console.log(isSubQuence('aec', 'abcde'))


// 17.股票问题-买卖股票的最佳时机
// 题解：只能交易一次，找到所有的
// 思路：类比求子串和这里是求差
// 注意：出现小于minIndex的minIndex更新，再计算每个位置的最大差值 max = Math.max(max, arr[i] - arr[minIndex])
var findMaxPrice = (arr) => {
  let minIndex = 0;
  let max = 0;
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < arr[minIndex]) {  // 不是比较相邻，是最小
      minIndex = i
    }
    max = Math.max(max, arr[i] - arr[minIndex])
  }
  return max
}
console.log(findMaxPrice([4, 2, 1, 5, 9]))

// 18.买卖股票的最佳时机
// 题解：可以多次买卖, 没一次计算差值，正添加，负数+0
// 思路：可以多次买卖, 没一次计算差值，正添加，负数+0
// 注意：不停叠加利润
var maxPrice = (arr) => {
  let max = 0;
  for (let i = 1; i < arr.length; i++) {
    max += Math.max(0, arr[i] - arr[i - 1])
  }
  return max
}
console.log(maxPrice([7, 1, 5, 3, 6, 4]))

// 19.买卖股票的最佳时机
// 多次买入卖出，收手续费，手里有股票时必须卖出了才能继续买入
// 题解：有利润时，将利润加入到结果中，并且将minPrice赋值为当前价格减去手续费，这样如果下一个price更高时，就可以直接将两个price的差值加入到结果中，不用再扣除手续费。
// 思路：price[i] + fee < buy 假性卖出，也就是假性买入
// 注意：假性卖出也就是假性买入
var maxPrice2 = (price, fee) => {
  let buy = price[0] + fee;
  let max = 0;
  for (let i = 1; i < price.length; i++) {
    if (price[i] + fee < buy) {
      buy = price[i] + fee // 更新最低买入
    } else if (price[i] > buy) {
      max += price[i] - buy // 持续叠加利润
      buy = price[i]
    }
  }
  return max
}
console.log(maxPrice2(prices = [1, 3, 2, 8, 4, 9], fee = 2))

// 20. 单调递增的数字
// 题目的意思？？？：当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
// 题解：给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 
// 思路：找到位数最高的一个索引将其-1，后面的全部变为9
// 注意：第一个循环是倒序，第二个开始是第一个找个flag
var increasingDigits = (n) => {
  let str = n.toString()
  let arr = str.split('').map(i => +i)
  let flag = str.length // 注意flag在在索引之外
  for(let i = arr.length-1; i > 0; i--){
    console.log(arr[i-1], arr[i])
      if(arr[i-1] > arr[i]){ // 已
          arr[i-1] = arr[i-1] - 1
          arr[i] = 9
          flag = i
          console.log(str, arr[i-1], arr[i], flag)
      }
  }

  for(let i = flag; i < arr.length; i++){
      arr[i] = 9
  }

  return +arr.join('')
}
console.log(increasingDigits(1234))


